const PAPER_MONEY: [u32; 8] = [100,50,30,20,10,5,2,1];

pub fn dp_rec_mc(mut amount: u32) -> u32 {
    // 思路：贪心地选择可以选择的最大面值，可以证明当任意两个小面值的和都不大于大面值时，贪心方案是最优的
    let mut cnt = 0;
    let mut type_index = 0;
    while amount > 0 {
        cnt += amount / PAPER_MONEY[type_index];
        amount %= PAPER_MONEY[type_index];
        type_index += 1;
    }
    cnt
}
